package com.github.yangyishe.p100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 49. 字母异位词分组
 * https://leetcode.cn/problems/group-anagrams/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 *
 * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
 *
 *
 *
 * 示例 1:
 *
 * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 * 示例 2:
 *
 * 输入: strs = [""]
 * 输出: [[""]]
 * 示例 3:
 *
 * 输入: strs = ["a"]
 * 输出: [["a"]]
 *
 *
 * 提示：
 *
 * 1 <= strs.length <= 104
 * 0 <= strs[i].length <= 100
 * strs[i] 仅包含小写字母
 */
public class Problem49 {
    public static void main(String[] args) {
        String[] strs=new String[]{"cab","tin","pew","duh","may","ill","buy","bar","max","doc"};


        Problem49 problem49 = new Problem49();
        List<List<String>> lists = problem49.groupAnagrams(strs);
        System.out.println(lists);
    }

    /**
     * 思路:
     * 构建一个类哈希表, 使字母异位词的哈希值相等
     *
     * 类哈希方法:
     * 1. 遍历字符串的所有字符, 获得一个字符串对应的数量类哈希表
     * 2. 将这个类哈希表, 转化为一个字符串(理论上转成一个数字也可以, 但太大了), 或者使用一个新类包裹住, 并记录比较方法
     * 此处为了使逻辑简单, 及后续再取哈希方便, 使用字符串的方式实现
     * 3. 对相同类哈希值相等的字符串, 规定到相同的集合内
     *
     * 本质是嵌套两层hash
     *
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<Long,List<String>> map=new HashMap<>();

        long[] hashKeys=new long[26];
        for(int i=0;i<26;i++){
            hashKeys[i]=new Object().hashCode();
        }

        for (String str : strs) {
            Long anagramHash = anagramHash(str,hashKeys);
            map.putIfAbsent(anagramHash,new ArrayList<>());
            map.get(anagramHash).add(str);
        }

        List<List<String>> resultList = new ArrayList<>(map.values());

        return resultList;
    }

    /**
     * 利用hash值唯一性, 快速构建新的hash方法
     * @param s
     * @param hashKeys
     * @return
     */
    public long anagramHash(String s,long[] hashKeys){
        long l=0;
        for(char c:s.toCharArray()){
            l+=hashKeys[c-'a'];
        }

        return l;
    }

    public String anagramHash2(String s){
        int[] ints=new int[26];
        for(char c:s.toCharArray()){
            ints[c-'a']++;
        }
        StringBuilder sb=new StringBuilder();
        for(int i:ints){
            sb.append(i).append("-");
        }
        return sb.toString();
    }
}

